Metric dimension (graph theory)

In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

Contents

Detailed definition

For an ordered subset W = \{w_1, w_2,\dots w_k\} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the ordered k-tuple r(v|W) = (d(v,w_1), d(v,w_2),\dots,d(v,w_k)), where d(x,y) represents the distance between the vertices x and y. The set W is a resolving set (or locating set) for G if every two vertices of G have distinct representations. The metric dimension of G is the minimum cardinality of a resolving set for G. A resolving set containing a minimum number of vertices is called a basis (or reference set) for G. Resolving sets were introduced independently by Slater (1975) and Harary & Melter (1976).

Trees

Slater (1975) provides the following simple characterization of the metric dimension of a tree. If the tree is a path, its metric dimension is one. Otherwise, let L denote the set of degree-one vertices in the tree (usually called leaves, although Slater uses that word differently). Let K be the set of vertices that have degree greater than two, and that are connected by paths of degree-two vertices to one or more leaves. Then the metric dimension is |L| − |K|. A basis of this cardinality may be formed by removing from L one of the leaves associated with each vertex in K.

Properties

In Chartrand, Eroh & Oellermann (2000), it is proved that:

Khuller, Raghavachari & Rosenfeld (1996) prove the inequality n\leq D^{\beta-1}%2B\beta for any n-vertex graph with diameter D and metric dimension β.

References